#include <stdlib.h>
#include <stdio.h>
#include "globals.h"
#include "list_node.h"

ListNode* list_get_node_at_index(LinkedList* list, int index);


LinkedList* create_LinkedList() {
	/*
	 * This function is O(1).
	 */
	LinkedList* list = malloc(sizeof(LinkedList));
	list->head = malloc(sizeof(ListNode));
	list->tail = malloc(sizeof(ListNode));

	list->size = 0;
	list->head->next = list->tail;
	list->head->prev = NULL;
	list->tail->prev = list->head;
	list->tail->next = NULL;

	return list;
}

int destroy_LinkedList(LinkedList* list) {
	/*
	 * This function is O(n).
	 */
	if (list == NULL) {
		puts("List is NULL!");
		exit(-1);
	}
	while (!list_is_empty(list)) {
		list_remove(list);
	}
	free(list->tail);
	free(list->head);
	free(list);

	return TRUE;
}

int list_add_at_index(LinkedList* list, int index, int data) {
	/*
	 * This function is O(n/2) since at most it will iterate through half
	 * the list.  The utility method it calls is O(n/2) and this method is
	 * O(1)...O(1) * O(n/2) = O(n/2).
	 */
	if (list == NULL) {
		puts("List is NULL");
		exit(-1);
	} else if (index > list->size || index < 0) {
		puts("Index out of bounds!");
		exit(-1);
	}

	ListNode* current = list_get_node_at_index(list, index);

	ListNode* temp = malloc(sizeof(ListNode));
	temp->data = data;
	temp->next = current;
	temp->prev = current->prev;
	current->prev->next = temp;
	current->prev = temp;
	list->size++;
	return TRUE;
}

int list_add(LinkedList* list, int data) {
	/*
	 * This function is O(1).
	 */
	if (list == NULL) {
		return FALSE;
	}

	ListNode* temp = malloc(sizeof(ListNode));
	temp->next = list->tail;
	temp->prev = list->tail->prev;
	temp->prev->next = temp;
	list->tail->prev = temp;
	temp->data = data;
	list->size++;

	return TRUE;
}

int list_remove_from_index(LinkedList* list, int index) {
	/*
	 * For the same reasons at list_add_at_index(list, index, data), this
	 * function is O(n/2)
	 */
	if (list == NULL) {
		puts("list is NULL!\n");
		exit(-1);
	} else if (index < 0 || index > list->size - 1) {
		puts("index out of bounds!\n");
		exit(-1);
	}

	//if the index is in the first half, iterate from start.
	//avoid divide by zero erros.
	ListNode* current = list_get_node_at_index(list, index);

	current->prev->next = current->next;
	current->next->prev = current->prev;
	int value = current->data;
	free(current);
	list->size--;
	return value;
}

int list_remove(LinkedList* list) {
	/*
	 * This function is O(1).
	 */
	if (list == NULL || (list != NULL && list->size == 0)) {
		puts("List provided is NULL or empty, exiting...");
		exit(-1);
	}
	ListNode* skipped = list->head->next;
	list->head->next = skipped->next;
	list->head->next->prev = list->head;
	int value = skipped->data;
	free(skipped);
	list->size--;
	return value;
}

void list_print(LinkedList* list) {
	/*
	 * This function is O(n).
	 */
	if (list == NULL) {
		puts("NULL list provided!");
		return;
	}
	if (list->size == 0) {
		puts("List is empty");
		return;
	}
	ListNode* current = list->head->next;
	while (current != list->tail) {
		printf("%i", current->data);
		if (current->next != list->tail) {
			printf(", ");
		}
		current = current->next;
	}
	printf("\n");
}

int list_is_empty(LinkedList* list) {
	/*
	 * This function is O(1).
	 */
	if (list == NULL) {
		printf("NULL list provided!");
		exit(-1);
	}
	if (list->size == 0) {
		return TRUE;
	} else {
		return FALSE;
	}
}

ListNode* list_get_node_at_index(LinkedList* list, int index) {
	ListNode* current;
	//if the node is to be inserted in the first half, the funky
	//if statement is to prevent divide by zero errors.
	if (index == 0 || (index != 0 && ((double)list->size) / index >= 2)) {
		int i;
		current = list->head->next;
		for (i = 0; i < index; i++) {
			current = current->next;
		}
	} else {
		//index is in second half
		current = list->tail;
		int i;
		for (i = list->size; i > index; i--) {
			current = current->prev;
		}
	}
	return current;
}
